// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import "fmt"

func main() {
	// 背包的最大承重量
	W := 10
	// 放置在背包中的物品的重量
	weights := []int{2, 3, 4, 5}
	// 放在背包里的物品的价值
	values := []int{3, 4, 5, 6}
	// 调用背包函数解题并打印结果
	fmt.Println(knapsack(W, weights, values))
}

// 返回背包中可以放置的最大值
func knapsack(W int, weights, values []int) int {
	// 数组的长度
	n := len(weights)
	// 创建一个n+1行W+1列的二维切片
	dp := make([][]int, n+1)
	for i := range dp {
		dp[i] = make([]int, W+1)
	}
	// 使用动态规划填充二维切片
	for i := 1; i <= n; i++ {
		for w := 1; w <= W; w++ {
			if weights[i-1] > w {
				// 如果第 i 件物品的重量大于最大重量 w，则第 i 件物品不能放入背包
				dp[i][w] = dp[i-1][w]
			} else {
				// dp[i-1][w]表示使用前i-1个物品和不包括第i个物品的最大权重
				// dp[i-1][w-weights[i-1]]表示最大权重为 w-weights[i-1] 的可以获得的值
				dp[i][w] = max(dp[i-1][w], dp[i-1][w-weights[i-1]]+values[i-1])
			}
		}
	}
	// 使用所有项目和最大重量 W 可以得到的最大值是解决方案
	return dp[n][W]
}

// 接受两个整数 a 和 b 并返回两个整数中的最大值
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

//$ go run knapsack.go
//13
